In recent years, attention has been drawn to distributed computing aimed at efficient use of resources and the like. Such distributed computing is called cloud and offers various types of services. In distributed computing, a plurality of computing devices constituting a cell executes tasks instructed by a client in coordination with one another. It is thus necessary to achieve consensus among the computing devices. One example of algorithms for achieving consensus in this manner is the Paxos algorithm described in, for example, PLT 1 through PLT 3.
The Paxos algorithm is a consensus algorithm according to which servers constituting a cell act as a leader or an agent. The Paxos algorithm works such that, before the distributed computing system executes a predetermined command, it is checked whether or not a majority of the servers constituting the cell agrees on the execution of the command; if consensus is achieved to that effect, the execution is started. Use of such an algorithm allows easily synchronizing the computing devices, thus achieving high availability.
To be more specific, according to the Paxos algorithm (Simple Paxos), a leader that has received a request from a client transmits a round value, which is a proposal number indicating the details of Paxos consensus, to other servers acting as agents [proposal of round value].
Each agent compares a round value stored therein with the round value received from the leader. If the stored round value is greater than the received round value, each agent returns a denial signal to the leader. If not, each agent accepts the transmitted proposal and returns an accept signal [acceptance].
When the number of agents from which the leader has received the accept signal is greater than or equal to a number obtained by subtracting one from a majority of all servers (because the leader itself agrees on the execution), the leader selects a predetermined one of proposals returned from the agents, if any. In the absence of such proposals, the leader selects the proposal made by the client, and then transmits the selected proposal to other agents with a round value appended thereto. The agents compare the round value stored therein with the round value received from the leader. If the stored round value is greater than the received round value, the agent returns a denial signal to the leader. If not, the agent accepts the transmitted proposal and returns an approve signal [approval].
When the number of agents from which the leader has received the approve signal is greater than or equal to a number obtained by subtracting one from a majority of all servers (because the leader itself agrees on the execution), the leader determines that consensus has been achieved [achievement of consensus] (the Paxos algorithm guarantees that this determination is not overturned).
Then, the leader instructs execution of the instance, and the processing moves to the execution of the instance on which consensus has been achieved [execution of instance].
Subsequently, instances are continuously executed. Upon execution of each instance, processing such as proposal of a round value, acceptance, approval, achievement of consensus (hereinafter, “round-winning”), and execution of the instance is performed again. This method is extremely inefficient because a sequence of round-winning processes must be performed for each instance.
In order to solve the above problem, a Multi-Paxos scheme has been proposed whereby, once consensus has been achieved on a round value, it is assumed that consensus has been reached on winning the round, and the processing moves to achievement of consensus on an instance and execution of the instance. The Multi-Paxos scheme is advantageous in that, once processing from proposal of a round value through achievement of consensus on the round value has been performed, these steps become unnecessary.